package edu.siu.math.egut.util;

import java.io.Serializable;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.WeakHashMap;

import com.sun.java_cup.internal.runtime.Scanner;

import edu.siu.math.egut.main.OutputStyle;

/**
 * The Class Monomial is essentially a representation of the mathematical object of the same
 * name:  a finite formal product of integral powers of variables.  These powers can be 
 * positive or negative, which is something of a deviation from standard usage.  One may 
 * wish to regard our Monomials as "Laurent monomials."  If a given variable does not appear
 * among those variables used to express a given monomial, one may adopt the convention 
 * that it has an exponent of zero in that monomial.  
 *  
 * Under the current implementation, variables are represented as Strings.  Often, for semantic reasons
 * we treat the String as the "name" of the variable. 
 */ 
 /* TODO create a Variable class which validates, preventing the use of 
 * - the empty String
 * - math operators + - * % ^ and / 
 * - whitespace 
 * - any specific strings (e.g., _RESERVED) which are used internally and must be barred from user use
 * 
 */
/* TODO "read" could still be smarter.

/**
 * This class supports multiple variables (as Strings) with integer
 * coefficients . Instantiations of this class are immutable, and as such there
 * is never more than one copy of each distinct monomial. This sharing of
 * objects is aimed at reducing memory usage in large scale applications. This
 * class is heavily based on a similar program written in C++ by Joseph Hundley.
 * 
 * This class also implements comparable which is used by the polynomial class
 * for sorting the composing monomials.
 * 
 * A variable may be any string, however using strange strings will make output
 * less clear to read.  Use of the string "_RESERVED" may cause errors in the 
 * method "commutator" from class "Group."
 * 
 * A monomial may be output using the function "toString()."
 * 
 * @author Joe Pleso
 * @author Joseph Hundley
 */
final public class Monomial implements Comparable<Monomial>, Serializable {

    /**
     * Objects in most of the main utility classes of the Egut package are serializable, allowing 
     * the main programs to save the users work.  With monomial to date we have done the bare minimum:
     * we added the clause "implements Serializable" to the class declaration and we gave it a
     * serialVersionUID.
     */
    private static final long serialVersionUID = 137L;
    /**
     * The String constant "_RESERVED" is used internally by the egut package. It should
     * not be used by classes that use monomial. Doing so will result in
     * strange results.
     */
    public static final String RESERVED_VARIABLE = "_RESERVED";
    /**
     * We maintain a store of monomial objects.  A given polynomial has symbolic links to objects
     * in the store.  Semantically, the first term in x+y and the second term in x^2+x are the 
     * same monomial.  If I make the substitution x -> (a+b) in the first polynomial, it does not 
     * change the monomial x.  It changes the polynomial x+y so that its first monomial is the 
     * monomial "a" instead of the monomial "x."
     * 
     */
    final static private Map<Monomial, Object> monomials = new WeakHashMap<Monomial, Object>();
    /**
     * Returns the monomial with the specified variables and exponents. There is
     * at most one monomial object, which is shared, with any specific
     * combination of variables and exponents. This method checks if the
     * requested monomial exists. If not it creates it and adds it to the store
     * of active monomials. Either way the reference to the specified object in
     * the store (either existing from the store or the one just created
     * respectively) is returned. When the monomial is no longer in use (as
     * determined by the JVM), it is removed from the store. This process is
     * completely transparent.
     * 
     * @param pairs Map which contains pairs of variables and corresponding
     *                integer exponents
     * 
     * @return the Monomial object that has the same set of variables
     */
    public static Monomial create(Map<String, Integer> pairs) {
	
	// check whether the monomial the user wants is already there in the store,
	// if it is, pass back the copy from the store.
	for (Monomial m : monomials.keySet()) {
	    if (pairs.equals(m.v))
		return m;
	}
	// if not, call the Constructor.
	return new Monomial(pairs);
    }
    
    /**
     * Creates a monomial consisting of a single variable raised to the first power.
     * 
     * @param s string name for the variable 
     * @return the monomial s^1.
     */
    public static Monomial create (String s){
	// create a map
	  Map<String, Integer> preMonomial = new HashMap<String, Integer>();
	  // put in the desired pair:  variable s, exponent 1.
	  preMonomial.put(s,1);
	  // pass that map to the map<String, Integer> version of create.
	  return create(preMonomial);
  }
    
    /**
     * Creates a monomial consisting of a specified variable raised to a specified power.
     * 
     * @param s String, interpreted as variable
     * @param e Integer, interpreted as exponent
     * @return  the Monomial object representing the monomial s^e.
     */
    public static Monomial create (String s, int e){
	// create map
	  Map<String, Integer> preMonomial = new HashMap<String, Integer>();
	  //  check that the exponent is not zero.   only do something if the exponent is not zero
	   
	  if(e != 0)
	      // assuming the monomial is nonzero, put the data into the map.
	      preMonomial.put(s,e);
	  /* pass the data to the map version of create.  Note that if this method is passed an 
	   * exponent of zero it passes the empty map to the map version of create.  This models
	   * our view that x^0 and y^0 are the same Monomial:  the trivial or empty monomial.
	   * (One might think of this Monomial as "1.")
	   */
	  return create(preMonomial);
  }
   
    /**
     * Reads a string  into a monomial.
     * The expected form is a sequence of variable-exponent pairs.  
     * Within each pair, the separation between the variable and the exponent is a caret (^).
     * The separation between pairs can be marked by whitespace or an asterisk (*) or, 
     * in some circumstances, not at all.  
     * 
     * Variable names may not start with a digit or contain  ., /,\,*,^,+,-,(, or )
     * 
     * Parentheses, brackets, or braces, may be used to enclose an exponent, but other than  
     * that, exponents should be integers (positive or negative) written in decimal notation.
     * 
     * (For example, "5-3" will not be read as "2."  It may cause an exception to be thrown, 
     * or one may end up with a variable whose name begins "-3".)
     * 
     * Nested delimiters in an exponent will produce an exception.  
     * 
     * Whitespace in exponents will produce errors. (Because whitespace is read as indicating separation 
     * between pairs.)
     * 
     * @param s the string to be read
     * @return the monomial
     * @throws MonomialReadException thrown if attempts to interpret the string as a Polynomial prove unsuccessful. 
     */
    
    public static Monomial read (String s) throws MonomialReadException {
	
	  Map<String, Integer> preMonomial = new HashMap<String, Integer>();
	  /*As a general principal, whitespace will be interpreted as separating factors
	   * in the product.  
	   * 
	   * One exception is that whitespace might be placed around 
	   * a caret (^) by the user for readability or by force of habit. 
	   * 
	   * If what precedes the whitespace does not make sense as a variable, or if what
	   * follows the whitespace does not make sense as a number, then we won't be able 
	   * to parse this string as a polynomial, but errors of that sort can be detected at 
	   * a later stage.
	   */
	  
	  /* remove whitespace around ^, -, (,),[,{, or to the left of ],}.  
	   * Either ] or } might appear as the last character in a variable
	   * name (as part of a notation for subscripts).  Hence, whitespace
	   * to the right of these symbols may be essential for correct interpretation,
	   * and should not be removed.
	   */
	  s = s.replaceAll("\\s*\\^\\s*", "\\^");
	  s = s.replaceAll("\\s*\\-\\s*", "\\-");
	  s = s.replaceAll("\\s*\\)\\s*", "\\)");
	  s = s.replaceAll("\\s*\\(\\s*", "\\(");
	  s = s.replaceAll("\\s*\\]", "\\]");
	  s = s.replaceAll("\\s*\\[\\s*", "\\[");
	  s = s.replaceAll("\\s*\\}", "\\}");
	  s = s.replaceAll("\\s*\\{\\s*", "\\{");
			     
	  
	  // break into pieces according to * and whitespace, both of which are 
	  // interpreted as multiplication.
	  String[] factors = s.split("[\\*\\s]");
	  int numberOfFactors = factors.length;

	  /* we still entertain the possibility that the individual substrings might 
	   * actually contain several factors.  for example, if the user has entered a^2b^3c^7, with 
	   * no *'s and no spaces, it should be read correctly.
	   * 
	   */
	  for( int j = 0 ; j < numberOfFactors; j++)
	  {
	      while (!(factors[j].length() == 0)) {
		  
		  // remove whitespace at both ends
		factors[j] = factors[j].trim();
		
		// split at the first occurence of "^". 
		String[] baseExpPair = factors[j].split("\\^", 2);
		/* REMARK:  When writing monomials, it is permissible to omit the exponent 1.
		 * That is "x^1" can be expressed more simply as "x."  If the factor is "x"
		 * our baseExpPair will not actually be a pair!  This is handled below.
		 */
		

		//everything before the first "^" is taken to be the "variable"
		
		// trim off the whitespace
		baseExpPair[0] = baseExpPair[0].trim();
		
		/* Check that this makes sense for a variable. 
		 * We impose the following conditions:
		 * - not the empty string,
		 * - does not start with a digit
		 * - does not contain *, +, -, /, \, (,),<,>,=, ^
		 */
		
		checkVariableProperties(baseExpPair[0]);
		
		    
		
		
		/* the second piece of our pair should consist of an integral 
		 * exponent and, possibly, some additional factors which have 
		 * not been separated.  For example, if the input was a b^2c^3,
		 * our pair might be (b, 2c^3).  Next we want to split off the 
		 * exponent.
		 */
		int exponent;
		/* If the factor string did not contain a "^", then this factor is understood to 
		 * represent a single variable to the first power.
		 */
		if (baseExpPair.length == 1) {
		    exponent = 1;
		    factors[j] = "";// We're done with this factor.  When we reach the end of the while loop, we should exit. 
		} else {
		    /*we have a nontrivial second element in our "pair."  It should contain an integral 
		     * exponent and possibly some other factors.  We process it.
		     */
		    
		    // trim off whitespace at both ends.
		    baseExpPair[1] = baseExpPair[1].trim(); 
		    
		    int i = 0;/* this will be the iterator in a for loop.  
	 		*However, we want to be able to access its 
	 		* value AFTER exiting the for loop, so we initialize it before the for().
	 		* The for loop will be looking for the first non-digit, the presumed end 
	 		* of an integral exponent.  Digits might start at position 0, or at position 
	 		* 1 if the integer is negative, so that the first character is '-'.
	 		*/
		    
		    // Now to detect the exponent.  Break into cases based on the next character.
		    switch(baseExpPair[1].charAt(0))
		    {
		    case '(':
			// exponent should be everything until the corresponding right parenthesis 
			
			// if there is no right parenthesis... then we have a problem.
			if( baseExpPair[1].indexOf(')') == -1)
			    throw new MonomialReadException("unmatched parenthesis.");
			
			// otherwise, exponent is everything until the next right parenthesis
			try{ 
			exponent = Integer.parseInt(baseExpPair[1].substring(1, baseExpPair[1].indexOf(')')).trim());
			}catch(NumberFormatException e){
			    throw new MonomialReadException("parseInt can't handle "+ baseExpPair[1].substring(1, baseExpPair[1].indexOf(')')));			}
			
			// and the rest should be additional factors.
			factors[j] = baseExpPair[1].substring(baseExpPair[1].indexOf(')')+1);
			
			// and we're done with the switch
			break;
			
			
		    case '[':
			// exponent should be everything until the corresponding right bracket
			
			// if there is no right bracket... then we have a problem.
			if( baseExpPair[1].indexOf(']') == -1)
			    throw new MonomialReadException("unmatched bracket.");
			
			try{
			exponent = Integer.parseInt(baseExpPair[1].substring(1, baseExpPair[1].indexOf(']')).trim());
			}
			catch( NumberFormatException e){
			    throw new MonomialReadException("parseInt can't handle "+ baseExpPair[1].substring(1, baseExpPair[1].indexOf(']')));
			}
			factors[j] = baseExpPair[1].substring(baseExpPair[1].indexOf(']')+1);
			break;
			
		    case '{':
			// exponent should be everything until the corresponding right brace

			// if there is no right parenthesis... then we have a problem.
			if( baseExpPair[1].indexOf('}') == -1)
			    throw new MonomialReadException("unmatched brace.");
			try{
			exponent = Integer.parseInt(baseExpPair[1].substring(1, baseExpPair[1].indexOf('}')).trim());
			} catch(NumberFormatException e){
			    throw new MonomialReadException("parseInt can't handle "+baseExpPair[1].substring(1, baseExpPair[1].indexOf('}')));
			}
			
			factors[j] = baseExpPair[1].substring(baseExpPair[1].indexOf('}')+1);
			break;
			
			/* In the remaining cases, we think we have a string which starts with a representation of an 
			 * integer.  If this supposition is false, parse should fail.  A NumberFormatException() will
			 * be thrown by Integer.parseInt().  NumberFormatExceptions are unchecked, and we prefer to 
			 * have a checked exception thrown, so we catch the NumberFormatException and throw a
			 * MonomialReadException.
			 */

			
			
		    case '-':
			// ignore the minus and look for digits.
			i++;
			default:
			    // look for digits.
			    

				 //run through the characters of our string until a nondigit is encountered.		  
				 for (;
				 i<baseExpPair[1].length();
				 i++){
				     if (!Character.isDigit(baseExpPair[1].charAt(i)))
					 break;
				 }
				 //value of i is now equal to the first non-digit. 
			
			// set the exponent.  To do so, parse a substring into an integer.  The substring should start 
			// at 0.  It should end at the integer i just computed
			// by the for loop.
			try{
			exponent = Integer.parseInt(
				baseExpPair[1].substring(0, i));
			} catch(NumberFormatException e){
			    throw new MonomialReadException("parseInt can't handle "+baseExpPair[1].substring(0, i));
			}
			
			/* If anything is left, the working hypothesis is that it is additional terms that 
			 * were run together with the one just processed. 
			 * E.g., we had a^2b^2c, and having split off the "a" as a variable and 
			 * the "2," the remainder is the "b^2c."
			 */
			factors[j] = baseExpPair[1].substring(i).trim();
			
			    
		    }// end switch
		 
		 
		 
		
		
	
		
	      }//end while factors[j].length() != 0
	      
		/* Suppose the same variable shows up twice in a monomial.  How do we handle that?  There are 
		 * two reasonable options:
		 * (1) conjecture that the user has made a typographical error, 
		 * (2) simply read x y x as x^2y.
		 * This implementation opts for (1), prioritizing error-detection, at the expense of 
		 * introducing finickyness.		 
		 */		
	      if (preMonomial.put(
		      baseExpPair[0], exponent) != null)
		  throw new MonomialReadException("Too many " + baseExpPair[0]);
	     
	      }

	  }
	  return create(preMonomial);

	     
	     
    }

    /**
     * Checks that a string satisfies certain properties making it suitable for a variable.
     * @param string a String to be checked
     * @throws MonomialReadException if the String does not satisfy the desired properties
     */
    private static void checkVariableProperties(String string) throws MonomialReadException {
	
	// should be nontrivial
	if(string.length()==0)
	    throw new MonomialReadException("variable of length zero");
	    
	// should not start with a digit
	if(string.substring(0,1).matches("[\\d]"))
	    throw new MonomialReadException("variable starts with digit.");
	
	
	// should not contain any of ./\*^+-()
	if(string.contains("."))
	    throw new MonomialReadException("variable contains period.");
	if(string.contains("/"))
	    throw new MonomialReadException("variable contains /.");
	if(string.contains("\\"))
	    throw new MonomialReadException("variable contains backslash.");
	if(string.contains("*"))
	    throw new MonomialReadException("variable contains *.");
	if(string.contains("^"))
	    throw new MonomialReadException("variable contains ^.");
	if(string.contains("+"))
	    throw new MonomialReadException("variable contains +.");
	if(string.contains("-")){ 
	    // the character - might plausibly appear in a subscript.
	    if( string.replaceAll("\\{.*?\\}", "").replaceAll("\\[.*?\\]", "").replaceAll("_\\s*\\-", "").contains("-"))
	    throw new MonomialReadException("variable contains - without subscript.");
	}
	if(string.contains("("))
	    throw new MonomialReadException("variable contains (.");
	if(string.contains(")"))
	    throw new MonomialReadException("variable contains ).");
	
	
    }

    final private SortedMap<String, Integer> v;

    private Monomial(Map<String, Integer> d) {
	// initialize the internal map v to be the given map d
	v = new TreeMap<String, Integer>(d);
	// add this Monomial to the registry
	monomials.put(this, null);
    }

    public boolean equals(Monomial m){
	return this == m;
    }
    
    public int compareTo(Monomial o) {
	if (o == null)
	    throw new NullPointerException();
	if (o == this)
	    return 0;
	/*
	 * mononomials of higher total degree come first. variables appear in
	 * alphabetical order. monomials of same total degree are sorted first
	 * by exponent of the "first" variable, then by the "second," etc.
	 * Total degree is computed by adding up the *absolute values* of the
	 * exponents.  
	 */

	if (this.getAbsoluteDegree() != o.getAbsoluteDegree())
	    return this.getAbsoluteDegree() - o.getAbsoluteDegree();

	Iterator<Map.Entry<String, Integer>> oI = o.v.entrySet().iterator();

	for (Map.Entry<String, Integer> tE : v.entrySet()) {
	    Map.Entry<String, Integer> oE = oI.next();
	    if (!tE.getKey().equals(oE.getKey()))
		return tE.getKey().compareTo(oE.getKey());
	    if (!tE.getValue().equals(oE.getValue())){
		
		return -tE.getValue() + oE.getValue();
	    }
	}
	
	// If we get to this point in this method, it means that this and o have 
	// the same degree and every variable of this appears in o with the same degree.
	// In such a circumstance, this and o are the same monomial and o== this should
	// have evaluated to true.
	
	// one possible diagnosis is that serialization and deserialization has led to 
	// a monomial slipping through the cracks of the registry.  
	System.out.println("Comparison failure." + this + "\n" + o);
	throw new RuntimeException();

    }
    public int verboseCompareTo(Monomial o) {
	if (o == null){
	    System.out.println("can't compare to null.");
	    throw new NullPointerException();
	}
	if (o == this){
	    System.out.println("identity (==)");
	    return 0;
	}
	/*
	 * mononomials of higher total degree come first. variables appear in
	 * alphabetical order. monomials of same total degree are sorted first
	 * by exponent of the "first" variable, then by the "second," etc.
	 * Total degree is computed by adding up the *absolute values* of the
	 * exponents.  
	 */

	if (this.getAbsoluteDegree() != o.getAbsoluteDegree()){
	    System.out.println("difference of absolute degrees.");
	    return this.getAbsoluteDegree() - o.getAbsoluteDegree();
	}

	Iterator<Map.Entry<String, Integer>> oI = o.v.entrySet().iterator();

	for (Map.Entry<String, Integer> tE : v.entrySet()) {
	    Map.Entry<String, Integer> oE = oI.next();
	    if (!tE.getKey().equals(oE.getKey())){
		System.out.println("comparison of keys: " + tE.getKey() + " compare to "
			+ oE.getKey() + " " + tE.getKey().compareTo(oE.getKey()));
		return tE.getKey().compareTo(oE.getKey());
	    }
	    if (tE.getValue() != oE.getValue()){
		System.out.println("comparison of values: "
			+ tE.getValue() +" "+ oE.getValue()
			+ (tE.getValue() == oE.getValue())
			+ (tE.getValue().equals(oE.getValue())) );
		return -tE.getValue() + oE.getValue();
	    }
	}
	
	// If we get to this point in this method, it means that this and o have 
	// the same degree and every variable of this appears in o with the same degree.
	// In such a circumstance, this and o are the same monomial and o== this should
	// have evaluated to true.
	
	// one possible diagnosis is that serialization and deserialization has led to 
	// a monomial slipping through the cracks of the registry.  
	System.out.println("Comparison failure." + this + "\n" + o);
	throw new RuntimeException();

    }

    /* THIS IS A DEFUNCT METHOD for factoring out a power of a variable....
     * It doesn't make much sense with negative exponents...
     * ---------------------------
     * Factor out one power of a single variable. This can only be called if the
     * monomial is not independent of the variable.
     * 
     * @param x  the name of the variable to be factored out
     * 
     * @return the monomial representation of the new monomial
     * @throws MonomialVariableMissingException   if the monomial is independent of the specified variable
     */
 /*   public Monomial factorOut(String x) throws MonomialVariableMissingException {
	if (isIndependentOf(x))
	    throw new MonomialVariableMissingException(x);
	SortedMap<String, Integer> newV = new TreeMap<String, Integer>(v);
	Integer newExponent = v.get(x) - 1;

	if (newExponent == 0)
	    newV.remove(x);
	else
	    newV.put(x, newExponent);

	return create(newV);

    }
*/
    /**
     * This method returns the sum of the absolute values of the exponents in this monomial.
     * 
     * @return the "degree" of the monomial
     */
    public int getAbsoluteDegree() {
	int sum = 0;
	
	
	for (Integer i : this.v.values())
	    sum += i* (i>0? 1:-1);// the bit in parentheses is the sign of i, so the absolute value of i is added.
	return sum;
    }
    /**
     * This method returns the sum of the exponents in this monomial.
     * 
     * @return the "degree" of the monomial
     */
    public int getDegree() {
	int sum = 0;
	for (Integer i : this.v.values())
	    sum += i;
	return sum;
    }
    
    /**
     * This method determines the exponent of a specified variable in the monomial which calls it.
     * @param s String, interpreted as the name of a variable
     * @return the exponent of s in the monomial, or 0 if s does not appear.
     */
    public int degreeIn( String s ){
	
	 return  v.containsKey(s)? v.get(s): 0;
	
	
    }
    
    /**
     * Get a variable that appears nontrivially.
     * @return a string which is one of the variables in the monomial.
     * 
     */
    public String getVar(){
	// since java.util.SortedMap comes equipped with a lastKey() method, it's convenient
	// to return the "last" String which appears as a variable in this monomial...
	return this.v.lastKey();
	
    }

    /**
     * Gets the exponent of a specified variable.
     * 
     * @param name   the name of the variable to check the exponent
     * 
     * @return the exponent of the variable we are checking
     */
    public int getExponent(String name) {
	
	/* Under the present implementation the data of a monomial is stored in an 
	 * object of class java.util.SortedMap with the "keys" being Strings and 
	 * the "values" being integers.  Each key is a variable and its value is 
	 * its exponent.  
	 * 
	 * java.util.SortedMap comes equipped with a "get" method which 
	 * returns the value of the key that it is passed, or "null" if 
	 * it is passed something which is not a key.
	 * 
	 * In our application, a String which is not a key is a variable 
	 * which does not appear in our Monomial.  According to standard
	 * convention, its exponent is zero.
	 * 
	 */
	return v.get(name) == null ? 0 : v.get(name);

    }

    
    /**
     * Returns the number of distinct variables that comprise this monomial.
     * (The number of variable, exponent pairs stored in this monomial)
     * 
     * @return the number of distinct variables that comprise this monomial
     * 
     * 
     * 
     */
    public int getSize() {
	return v.size();
    }

    /**
     * Checks if the Monomial is independent of a variable.
     * 
     * @param name    interpreted as the name of a variable
     * 
     * @return false if the specified variable appears in the Monomial and true
     *         if it does not.
     */
    public boolean isIndependentOf(String name) {
	return v.get(name) == null;

    }

    /* THIS IS A DEFUNCT METHOD
     * It could be restored, but would say that the monomial x^{-1} is linear.
     * It is not used by any other class or method at the moment.
     * -------------------------
     * Returns true if the monomial is linear -- i.e., consists of a single
     * variable raised to the first power-- and false otherwise.
     * 
     * @return the value of getDegree()==1
     */
 /*   public boolean isLinear() {
	return getDegree() == 1;

    }
*/
    // These can possibly be removed at some point
    /**
     * Returns true if the given variable appears in the monomial with an
     * exponent of 1, and false otherwise.
     * 
     * @param name    the name of the variable we are checking
     * 
     * @return true, if the exponent of the named variable is 1
     */
    public boolean isLinearIn(String name) {
	return v.get(name) != null && v.get(name) == 1;

    }

    /**
     * Multiplies this monomial with another and returns the resulting monomial.
     * 
     * 
     * 
     * @param b      the monomial by which to multiply
     * 
     * @return the monomial that represents the product
     */
    public Monomial multiply(Monomial b) {

	Monomial a = this;

	if (a.v.isEmpty())
	    return b;
	if (b.v.isEmpty())
	    return a;
	Map<String, Integer> newV = new TreeMap<String, Integer>(a.v);
	for (Map.Entry<String, Integer> entry : b.v.entrySet()) {
	    if (!newV.containsKey(entry.getKey()))
		newV.put(entry.getKey(), entry.getValue());
	    else {
		Integer newExponent = entry.getValue()
			+ newV.get(entry.getKey());
		if( newExponent != 0 )
		    newV.put(entry.getKey(), newExponent);
		else 
		    newV.remove(entry.getKey());
	    }
	}

	return create(newV);
    }

    /**
     * If m is a monomial and s is a String, regarded as a variable, then m.times(s) is the Monomial
     * obtained by multiplying m by s.
     * @param s String, treated as variable
     * @return (this monomial)*s
     */
    public Monomial times(String s){
	Map<String, Integer> newV = new TreeMap<String, Integer>(v);
	if(!newV.containsKey(s))
	    newV.put(s,1);
	else if(newV.get(s)==-1)
	    newV.remove(s);
	else
	    newV.put(s,newV.get(s)+1);
	return create(newV);
    }
    
    /**
     * Completely factors out a variable.
     * 
     * @param varName the name of the variable to be factored out
     * @return a monomial that is independent of the named variable. If the
     *         original monomial had this property, then the original monomial
     *         will be returned.
     */
    public Monomial remove(final String varName) {
	SortedMap<String, Integer> result = new TreeMap<String, Integer>(v);
	result.remove(varName);
	return create(result);
    }

    /**
     * Returns the string representation of the monomial.
     * 
     * @return the string
     * 
     * @see java.lang.Object#toString()
     */

    public String toString(OutputStyle sty) {
	
	final StringBuffer sb = new StringBuffer();
	for (final Map.Entry<String, Integer> x : v.entrySet()) {
	    sb.append(x.getKey());
	    if (x.getValue() != 1){
		switch(sty){
		case SCREEN:
		    sb.append("^" + x.getValue());
		    break;
		case MATHEMATICA:
		    sb.append("^(" + x.getValue()+")");
		    break;
		case TEX:
		    sb.append("^{" + x.getValue()+"}");
		    break;
		}
	    }
	    sb.append(" ");

	}
	
	return sb.toString();
    }
    public String toString() {
    return toString(OutputStyle.SCREEN);
    }
   public String toMachineReadableString(OutputStyle sty) {
	
	final StringBuffer sb = new StringBuffer();
	for (final Map.Entry<String, Integer> x : v.entrySet()) {
	    sb.append(x.getKey());
	    if (x.getValue() != 1){
		switch(sty){
		case SCREEN:
		    sb.append("^" + x.getValue());
		    break;
		case MATHEMATICA:
		    sb.append("^(" + x.getValue()+")");
		    break;
		case TEX:
		    sb.append("^{" + x.getValue()+"}");
		    break;
		}
	    }
	    sb.append("*");

	}
	
	sb.deleteCharAt(sb.lastIndexOf("*"));
	return sb.toString();
    }

    /**
     * Checks whether negative exponents show up in a monomial.  If m is a monomial, then m.hasNegativeExponents() returns
     * true if and only if there is some variable which appears in the finite product m with a negative exponent.
     * @return true if any exponent is negative
     */
    public boolean hasNegativeExponents() {
	for(int i: this.v.values())
	    if(i<0)
		return true;

	return false;
    }

    /**
     * Returns the variables that appear in m, as an object of class java.util.Set.
     * @return a Set of Strings containing all variables which appear.
     */
    public Set<String> getVariables() {
	return v.keySet();
    }

    /**
     * Keeps the monomial registry up to date in the presence of serialization and deserialization.
     * 
     * @param m Monomial, 
     * @return m if it appears in the registry. If not, extract the 
     * underlying data, and feed it to create, then return the 
     * "registered" monomial with the same data.
     * 
     */
    public static Monomial update(Monomial m) {
	if( monomials.containsKey(m))
	    return m;
	else
	    return Monomial.create(m.v);
	
    }

    /**
     * Raises a monomial to a (positive or negative) integer power.
     * If m is a monomial and n an integer then m.raisTo(n) is m^n.
     * @param power desired exponent
     * @return m^power
     */
    public Monomial raiseTo(final int power) {
	Map<String, Integer> newData = new TreeMap<String, Integer>();
	for( Map.Entry<String, Integer> x: v.entrySet() ){
	    newData.put(x.getKey(), x.getValue()*power);
	}
	return create(newData);
    }

    public Monomial replace(String var, String string) {
	TreeMap<String, Integer> newV = new TreeMap<String, Integer>(v);
	newV.remove(var);
	if( v.get(var )!= null)
	    newV.put(string, v.get(var));
	return Monomial.create(newV);
    }
    public Monomial new_replace(String var, String string) {
	
	if( v.get(var )== null)
	    return this;
	
	TreeMap<String, Integer> newV = new TreeMap<String, Integer>(v);
	newV.remove(var);
	newV.put(string, v.get(var));
	return Monomial.create(newV);
    }

}
